package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 32. 最长有效括号
 * @date 2024/12/9 11:06
 */
public class E32 {

    /**
     * <h3>方法一：用栈解决</h3>
     *
     * @param s 括号字符串
     * @return 最长有效括号长度
     */
    public int longestValidParentheses1(String s) {
        char[] charArray = s.toCharArray();
        LinkedList<Integer> stack = new LinkedList<>();
        int maxLength = 0;
        // 很重要的一点是用栈底元素维护有效括号子串的左边界（不包含），到时候计算有效括号子串长度需要用到它
        stack.push(-1); // 先压入一个-1，也就是索引0左边一个
        for (int i = 0; i < charArray.length; i++) {
            // 遇到左括号压入对应索引
            if (charArray[i] == '(') stack.push(i);
            // 遇到右括号，则尝试出栈左括号
            else {
                stack.pop();
                // 出栈后变为空了，说明出栈了栈底元素，没有左括号匹配，这时候需要维护一个新的栈底元素，就是当前元素的索引
                if (stack.isEmpty()) stack.push(i);
                // 出栈后栈不为空，说明有左括号匹配，此时栈顶元素就是当前右括号的匹配左括号的索引减一或者是栈底元素，如果是栈底元素，i - stack.peek()就是当前有效括号子串的长度
                else maxLength = Math.max(i - stack.peek(), maxLength);
            }
        }
        return maxLength;
    }

    /**
     * <h3>方法二：动态规划</h3>
     *
     * @param s 括号字符串
     * @return 最长有效括号长度
     */
    public int longestValidParentheses(String s) {
        char[] chars = s.toCharArray();
        int maxLength = 0;
        int[] dp = new int[s.length() + 1]; // 初始化dp数组，长度为s.length() + 1
        for (int i = 1; i <= s.length(); i++) {
            if (chars[i - 1] == ')') { // 使用char数组访问字符
                if (i >= 2 && chars[i - 2] == '(') {
                    // 简单情况：形如 "()" 的情况
                    dp[i] = dp[i - 2] + 2;
                } else if (i - dp[i - 1] - 1 > 0 && chars[i - dp[i - 1] - 2] == '(') {
                    // 复杂情况：形如 "((...))" 或者 ")...(...)" 的情况
                    dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }
}
